home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DJGPP / CBGRX103.ZIP / contrib / libgrx / src / scanpoly.c < prev    next >
Text File  |  1993-12-06  |  7KB  |  229 lines
  1. /**
  2.  ** SCANPOLY.C
  3.  **
  4.  **  Copyright (C) 1992, Csaba Biegl
  5.  **    820 Stirrup Dr, Nashville, TN, 37221
  6.  **    csaba@vuse.vanderbilt.edu
  7.  **
  8.  **  This file is distributed under the terms listed in the document
  9.  **  "copying.cb", available from the author at the address above.
  10.  **  A copy of "copying.cb" should accompany this file; if not, a copy
  11.  **  should be available from where this file was obtained.  This file
  12.  **  may not be distributed without a verbatim copy of "copying.cb".
  13.  **  You should also have received a copy of the GNU General Public
  14.  **  License along with this program (it is in the file "copying");
  15.  **  if not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  16.  **  Cambridge, MA 02139, USA.
  17.  **
  18.  **  This program is distributed in the hope that it will be useful,
  19.  **  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20.  **  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21.  **  GNU General Public License for more details.
  22.  **/
  23.  
  24. #include "grx.h"
  25. #include "libgrx.h"
  26. #include "clipping.h"
  27. #include "scale.h"
  28. #include "gmalloc.h"
  29.  
  30. typedef enum {
  31.     inactive,
  32.     active,
  33.     passed
  34. } edgestatus;
  35.  
  36. typedef struct _scansegment_ {
  37.     struct _scansegment_ *next;
  38.     int X1,X2;
  39. } scansegment;
  40.  
  41. typedef struct {
  42.     scansegment seg;
  43.     edgestatus  status;
  44.     int x1,x2,y1,y2;
  45.     int slope,error;
  46.     int dx,dy;
  47. } polyedge;
  48.  
  49. void _GrScanPolygon(int n,int pt[][2],
  50.     int is_XOR_color,
  51.     _GrPixelDrawProc pixelproc,
  52.     _GrLineDrawProc  borderproc,
  53.     _GrScanLineProc  scanfillproc,
  54.     void *fillarg)
  55. {
  56.     polyedge    *edgetable,*ep;
  57.     scansegment *firstpt,*firstseg,*pp,*sp,*prev;
  58.     int prevx,prevy;
  59.     int minx,maxx,miny,maxy;
  60.     int realedges;
  61.     int X1,X2,Y;
  62.     MOUSE_FLAG;
  63.  
  64. #define add_scanpoint(seg,x) do {                        \
  65.     X1 = (x);                                \
  66.     prev = NULL;                                \
  67.     for(pp = firstpt; pp != NULL; prev = pp,pp = pp->next)            \
  68.         if(pp->X1 >= X1) break;                        \
  69.     (seg)->next = pp;                            \
  70.     (seg)->X1 = X1;                                \
  71.     *(prev ? &prev->next : &firstpt) = (seg);                \
  72. } while(0)
  73.  
  74. #define add_scansegment(seg,x1,x2) do {                        \
  75.     char overlap = FALSE;                            \
  76.     X1 = (x1);                                \
  77.     X2 = (x2);                                \
  78.     prev = NULL;                                \
  79.     for(sp = firstseg; sp != NULL; prev = sp,sp = sp->next) {        \
  80.         if((sp->X1 <= X2) && (X1 <= sp->X2)) {                \
  81.         overlap = TRUE;                            \
  82.         if(X1 < sp->X1) sp->X1 = X1;                    \
  83.         if(X2 > sp->X2) {                        \
  84.             prev = sp;                            \
  85.             while((sp = sp->next) != NULL) {                \
  86.             if(sp->X1 > X2) break;                    \
  87.             if(sp->X2 > X2) X2 = sp->X2;                \
  88.             }                                \
  89.             prev->X2 = X2;                        \
  90.             prev->next = sp;                        \
  91.         }                                \
  92.         break;                                \
  93.         }                                    \
  94.         if(sp->X1 > X2) break;                        \
  95.     }                                    \
  96.     if(!overlap) {                                \
  97.         (seg)->next = sp;                            \
  98.         (seg)->X1 = X1;                            \
  99.         (seg)->X2 = X2;                            \
  100.         *(prev ? &prev->next : &firstseg) = (seg);                \
  101.     }                                    \
  102. } while(0)
  103.  
  104.     if((n > 1) && (pt[0][0] == pt[n-1][0]) && (pt[0][1] == pt[n-1][1])) n--;
  105.     if(n <= 2) {
  106.         if(n <= 0) return;
  107.         minx = pt[0][0];
  108.         miny = pt[0][1];
  109.         if(n == 1) {
  110.         MOUSE_BLOCK(CURC,minx,miny,minx,miny);
  111.         (*pixelproc)(minx,miny,fillarg);
  112.         }
  113.         else {
  114.         maxx = pt[1][0];
  115.         maxy = pt[1][0];
  116.         MOUSE_BLOCK(CURC,minx,miny,maxx,maxy);
  117.         (*borderproc)(minx,miny,maxx,maxy,fillarg);
  118.         }
  119.         MOUSE_UNBLOCK();
  120.         return;
  121.     }
  122.     edgetable = (polyedge *)_GrGetTempBuffer(sizeof(polyedge) * (n + 2));
  123.     if(edgetable == NULL) return;
  124.     /*
  125.      * Build the edge table. Store only those edges which are in the valid
  126.      * Y region. Clip them in Y if ncessary. Store them with the endpoints
  127.      * ordered by Y in the edge table.
  128.      */
  129.     prevx = pt[0][0];
  130.     prevy = pt[0][1];
  131.     minx = miny = 32000;
  132.     maxx = maxy = (-32000);
  133.     realedges = 0;
  134.     ep = edgetable;
  135.     while(--n >= 0) {
  136.         if(pt[n][1] >= prevy) {
  137.         ep->x1 = prevx;
  138.         ep->y1 = prevy;
  139.         ep->x2 = prevx = pt[n][0];
  140.         ep->y2 = prevy = pt[n][1];
  141.         }
  142.         else {
  143.         ep->x2 = prevx;
  144.         ep->y2 = prevy;
  145.         ep->x1 = prevx = pt[n][0];
  146.         ep->y1 = prevy = pt[n][1];
  147.         }
  148.         if(ep->y1 > _GrHiY) continue;
  149.         if(ep->y2 < _GrLoY) continue;
  150.         if(ep->y1 < _GrLoY) {
  151.         SCALE(X1,(ep->x1 - ep->x2),(ep->y2 - _GrLoY),(ep->y2 - ep->y1));
  152.         ep->x1 = ep->x2 + X1;
  153.         ep->y1 = _GrLoY;
  154.         }
  155.         if(ep->y2 > _GrHiY) {
  156.         SCALE(X2,(ep->x2 - ep->x1),(_GrHiY - ep->y1),(ep->y2 - ep->y1));
  157.         ep->x2 = ep->x1 + X2;
  158.         ep->y2 = _GrHiY;
  159.         }
  160.         if(ep->y1 < miny) miny = ep->y1;
  161.         if(ep->y2 > maxy) maxy = ep->y2;
  162.         if(ep->x2 > ep->x1) {
  163.         if(ep->x1 < minx) minx = ep->x1;
  164.         if(ep->x2 > maxx) maxx = ep->x2;
  165.         }
  166.         else {
  167.         if(ep->x1 > maxx) maxx = ep->x1;
  168.         if(ep->x2 < minx) minx = ep->x2;
  169.         }
  170.         ep->status = inactive;
  171.         realedges++;
  172.         ep++;
  173.     }
  174.     if(realedges == 0) return;
  175.     if(minx > _GrHiX) return;
  176.     if(maxx < _GrLoX) return;
  177.     MOUSE_BLOCK(CURC,minx,miny,maxx,maxy);
  178.     /*
  179.      * Scan for every row between ymin and ymax.
  180.      * Build a linked list of disjoint segments to fill. Rules:
  181.      *   (1) a horizontal edge in the row contributes a segment
  182.      *   (2) any other edge crossing the row contributes a point
  183.      *   (3) every segment between even and odd points is filled
  184.      */
  185.     for(Y = miny; Y <= maxy; Y++) {
  186.         firstpt  = NULL;
  187.         firstseg = NULL;
  188.         for(n = realedges,ep = edgetable; --n >= 0; ep++) {
  189.         switch(ep->status) {
  190.           case inactive:
  191.             if(ep->y1 != Y) break;
  192.             ep->dx = ep->x2 - ep->x1;
  193.             ep->dy = ep->y2 - ep->y1;
  194.             if(ep->dy == 0) {
  195.             add_scansegment(&ep->seg,
  196.                 ((ep->dx > 0) ? ep->x1 : ep->x2),
  197.                 ((ep->dx > 0) ? ep->x2 : ep->x1)
  198.             );
  199.             ep->status = passed;
  200.             break;
  201.             }
  202.             ep->slope = ep->dx / ep->dy;
  203.             if(ep->slope && !is_XOR_color)
  204.             (*borderproc)(ep->x1,ep->y1,ep->x2,ep->y2,fillarg);
  205.             if((ep->dx %= ep->dy) < 0) { ep->slope--; ep->dx += ep->dy; }
  206.             ep->error = ep->dy >> 1;
  207.             ep->status = active;
  208.           case active:
  209.             if((ep->y2 == Y) && (Y != maxy)) { ep->status = passed; break; }
  210.             add_scanpoint(&ep->seg,ep->x1);
  211.             if((ep->error -= ep->dx) < 0) { ep->x1++; ep->error += ep->dy; }
  212.             ep->x1 += ep->slope;
  213.             break;
  214.           default:
  215.             break;
  216.         }
  217.         }
  218.         while((pp = firstpt) != NULL) {
  219.         firstpt = pp->next->next;
  220.         add_scansegment(pp,pp->X1,pp->next->X1);
  221.         }
  222.         for(sp = firstseg; sp != NULL; sp = sp->next) {
  223.         (*scanfillproc)(sp->X1,sp->X2,Y,fillarg);
  224.         }
  225.     }
  226.     MOUSE_UNBLOCK();
  227. }
  228.  
  229.